1. Field of the Invention
The present invention relates to the field of halftone image production. In particular, the present invention relates to an apparatus and a method for creating a dither matrix in a less compute-intensive manner.
2. Description of Related Art
The use of halftone patterns is required whenever printing graphics with traditional inks upon paper. Halftone techniques arose because the continuously varying gradations of gray scale and colors cannot be directly printed by offset, dot-matrix, ink-jet, and other printer technologies that utilize the deposition of constant-shaded dots of black or colored ink. A common early halftone technique utilized a uniform screen, as shown in FIG. 1. A uniform screen segment 10 includes many cells, of which cell 12 is exemplary. Changing the density of gray scale using the uniform screen 10 may be performed by enlarging or shrinking the size of the ink dot corresponding to each cell. A light gray may be shown by making the ink dots relatively small in size. Conversely, a darker gray may be shown by making the ink dots relatively larger. The ink dot placed at a cell may be of any shape, with the square dots shown in FIG. 1 merely serving as examples.
The uniform screen 10 may be extended to cover an entire image. This is a simple process of uniformly extending the existing screen pattern, and requires no more than simple geometric calculations. However, the exemplary uniform screen 10 of FIG. 1 has certain visual drawbacks. The human visual system (HVS) is very sensitive at recognizing unintentional patterns, called artifacts, caused by the use of a halftone pattern. The HVS is most sensitive to slowly-varying in space (“low frequency”) artifacts and much less sensitive to rapidly-varying in space (“high frequency”) artifacts. The literature on the subject often characterizes the HVS as possessing a “low-pass filter”. Additionally, the HVS is much more sensitive to patterns falling on a horizontal or vertical line. In the FIG. 1 example, the cells line up along line 14. Line 14 forms an angle of θ degrees from a horizontal line 16. It is well-known in the art that the HVS is least sensitive to artifacts when θ is around ±45 degrees.
A better approach is illustrated in the dither pattern of FIG. 2. The dither pattern 20 includes a large number of cells, of which a typical one is cell 22. There are more blank spaces between the dots of dither pattern 20 so this would correspond to a light gray. More dots could be added for a darker shade of gray. The cells of dither pattern 20 have been arranged so that repetitive patterns, recognizable by the HVS, are minimized. It would appear on first glance that such a useful dither pattern 20 is “random”, but a truly random pattern would include dumps of cells and also empty spaces. Hence the dither pattern 20 would more correctly be described as evenly but not regularly patterned.
The dither pattern 20 of FIG. 2 corresponds to a particular percentage of cells being selected for ink-dot placement. In order to allow for differing percentages of cells being selected, a related dither matrix to dither pattern 20 may be created. A dither matrix is a dither pattern with an ordering scheme for including cells depending upon the ratio of ink dots filled cells to total cells required. For clarity, a dither matrix 30 is shown in FIG. 3a with a limited number of cells. In practice, a much larger number of cells would be defined and used in a dither matrix. To create dither matrix 30 from dither pattern 20, each cell such as exemplary cell 22 may have associated with it a threshold value, selected from a sequence from 1 through A, where A is the total number of cells in a dither pattern. For example, the threshold value stored in ordered cell 32 is the number 13. This means that if the ratio of dark cells to total cells is 13/A, then a proper pattern is for the printer to place ink dots at all ordered cells with a threshold value of 13 or less.
In order to extend the dither matrix 30 to cover an entire image, dither matrix 30 is replicated and applied as tiles. In FIG. 3b a typical tiling scheme is illustrated. A replicated copy matrix 40 of dither matrix 30 is placed at locations in a grid 42 covering the size of the image required.
A useful dither pattern such as dither pattern 20 is not easily created. One method of creating such a useful dither pattern, well-known in the art, is to use the technique known as error diffusion. In this method, first a two dimensional transfer function Vij that models the perceived responsiveness to patterns of the HVS is created. Vij is called a modulation transfer function (MTF). Then, a two-dimensional function pij that describes the location of all the selected cells in a given dither pattern is defined. Finally, a cost function that approximates the amount of artifacts seen by a human, depending upon Vij and a given pij, is created. In one embodiment, the cost function Cost(pij) may be given by Equation 1 below.                               Cost          ⁡                      (                          p              ij                        )                          =                              ∑                          i              =              1                        N                    ⁢                                           ⁢                                    ∑                              j                =                1                            N                        ⁢                                                   ⁢                                          V                2                            ⁢              ijPijP              *              ij                                                          Equation        ⁢                                   ⁢        1            where Pij is the discrete Fourier transform (DFT) of the given pattern pij. Other cost functions, known in the art, may be used.
One method of selecting the least-objectionable pattern pij for use in a dither pattern is to evaluate the cost function for all such patterns pij, and then select one of the pij corresponding to the minimum value of the cost function. This is not practicable. The number of such possible combinations pij representing M cells selected in a dither pattern of N by N cells is (N2!)/M!(N2-M)!. This is an enormous number even for smaller dither patterns such as 32 by 32, and the number increases substantially for desired dither patterns of 256 by 256 or even 1024 by 1024 cells. Evaluating Equation 1 for such large numbers of candidate patterns is computationally intensive, and for all but the smallest sizes of dither patterns is impractical with reasonable amounts of computer resources.